//环形链表
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast) return true;
        }
        return false;
    }
};

//二叉树展开为链表
class Solution {
public:
    vector<TreeNode*> node;
    void flatten(TreeNode* root) 
    {
        preorder(root);
        for(int i=1;i<node.size();i++)
        {
            TreeNode* prev=node[i-1];
            prev->left=nullptr;
            prev->right=node[i];
        }
    }
    void preorder(TreeNode* root)
    {
        if(root==nullptr) return; 
        node.push_back(root);
        preorder(root->left);
        preorder(root->right);
    }
};

//从前序与中序遍历序列构造二叉树
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        if(preorder.empty() || inorder.empty()) return nullptr;
        return process(preorder,0,preorder.size()-1,
                        inorder,0,inorder.size()-1);

    }
    TreeNode* process(vector<int>&preorder,int ps,int pe,
                    vector<int>&inorder,int is,int ie)
    {
        if(ps > pe || is>ie) return nullptr;
        //在前序遍历数组中 找到根节点
        TreeNode* newnode=new TreeNode(preorder[ps]);
        //在中序遍历数组中 找到他的根节点 他的左树和右树 在该节点的左右两侧
        for(int i=is;i<=ie;i++)
        //for(int i=0;i<inorder.size();i++)
        {
            if(inorder[i]==preorder[ps])
            {
                newnode->left=process(preorder,ps+1,i-is+ps,inorder,is,i-1);
                newnode->right=process(preorder,ps+i-is+1,pe,inorder,i+1,ie);
                break;
            }
        }
        return newnode;
    }
};
//单词搜索
class Solution {
public:
    bool res=false;
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    bool exist(vector<vector<char>>& board, string word) 
    {
        vector<vector<bool>>used(board.size(),vector<bool>(board[0].size(),0));
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(!res&&board[i][j]==word[0])
                {
                    dfs(board,used,word,0,i,j); 
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<char>>&board,vector<vector<bool>>&used,string word,int index,int curx,int cury)
    {
        if(res) return;
        if(index==word.size()-1)
        {
            res=true;
            return;
        }
       
        used[curx][cury]=true;
        for(int i=0;i<4;i++)
        {
            int newx=curx+arr[i][0];
            int newy=cury+arr[i][1];
            if(newx>=board.size() || newx<0 || newy>=board[0].size() || newy<0) continue;

            if(board[newx][newy]==word[index+1] && used[newx][newy]==false)
            {
                dfs(board,used,word,index+1,newx,newy);
            }
        }
        used[curx][cury]=false;
    }
    
};